package dp.备忘录dfs;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 预测赢家486.java
 * @createTime 2024年04月26日 16:26:00
 */
public class 预测赢家486 {
	public boolean predictTheWinner(int[] nums) {
		int[][] mem = new int[nums.length][nums.length];
		return dfs(0, nums.length - 1, nums, mem) >= 0;
	}

	public int dfs(int left, int right, int[] nums, int[][] mem) {
		//结束了返回
		if (left == right){
			return nums[left];
		}
		//存在记录
		if (mem[left][right] != 0){
			return mem[left][right];
		}
		//计算选左边时候的差值
		int leftNum = nums[left] - dfs(left+1, right, nums, mem);
		//计算选右边的差值
		int rightNum = nums[right] - dfs(left, right-1, nums, mem);
		//选择一个最大值
		mem[left][right] = Math.max(leftNum, rightNum);
		return Math.max(leftNum, rightNum);
	}
}
